package quicksort;

public class QuickSort {
    private int[] newArrayWithoutIndex(int[] sourceArray, int indexToRemove) {
        int[] newArray = new int[sourceArray.length - 1];

        for (int i = 0; i < sourceArray.length; i++) {
            if (i == indexToRemove)
                continue;
            if (i > indexToRemove)
                newArray[i - 1] = sourceArray[i];
            else
                newArray[i] = sourceArray[i];
        }
        return newArray;
    }

    private int[] addNewValueToArray(int[] sourceArray, int valueToAdd) {
        int[] newArray = new int[sourceArray.length + 1];

        System.arraycopy(sourceArray, 0, newArray, 0, sourceArray.length);
        newArray[newArray.length - 1] = valueToAdd;

        return newArray;
    }

    private int[] concatenate(int[] a, int pivot, int[] b) {
        int[] out = new int[a.length + b.length + 1];
        System.arraycopy(a, 0, out, 0, a.length);
        out[a.length] = pivot;
        System.arraycopy(b, 0, out, a.length + 1, b.length);
        return out;
    }

    /*
    function quicksort('array')
        if length('array') <= 1
            return 'array'  // an array of zero or one elements is already sorted
        select and remove a pivot value 'pivot' from 'array'
        create empty lists 'less' and 'greater'
        for each 'x' in 'array'
            if 'x' ≤ 'pivot' then append 'x' to 'less'
            else append 'x' to 'greater'
        return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls
    */

    public int[] quickSort(int sourceArray[]) {
        if (sourceArray.length <= 1)
            return sourceArray;

        int pivotIndex = sourceArray.length / 2;
        int pivotalValue = sourceArray[pivotIndex];

        int[] newArrayWithoutPivot = newArrayWithoutIndex(sourceArray, pivotIndex);

        int[] less = new int[0], greater = new int[0];

        for (int aNewArrayWithoutPivot : newArrayWithoutPivot) {
            if (aNewArrayWithoutPivot <= pivotalValue)
                less = addNewValueToArray(less, aNewArrayWithoutPivot);
            else
                greater = addNewValueToArray(greater, aNewArrayWithoutPivot);
        }

        return concatenate(quickSort(less), pivotalValue, quickSort(greater));
    }
}
